#!/usr/bin/env python3
"""
BOSS战策略优化器 - 使用分支限界算法
寻找在限定回合内击败BOSS的最小代价技能序列

分支限界策略：
- 状态空间搜索：每个状态包含BOSS血量、玩家资源、已用回合数
- 代价函数：f(n) = 已用回合数 + 预估剩余回合数
- 剪枝策略：丢弃代价超过当前最优解的节点
- 优先队列：优先探索代价最小的节点
"""

import heapq
import json
from typing import List, Dict, Tuple, Optional
from dataclasses import dataclass
from copy import deepcopy

@dataclass
class Skill:
    """技能定义"""
    name: str
    damage: int
    cost: int  # 消耗的资源（MP/能量等）
    cooldown: int  # 冷却回合数
    description: str

@dataclass 
class GameState:
    """游戏状态"""
    boss_hp: int           # BOSS当前血量
    player_resources: int  # 玩家剩余资源
    rounds_used: int       # 已使用回合数
    skill_cooldowns: Dict[str, int]  # 技能冷却状态 {技能名: 剩余冷却回合}
    skill_sequence: List[str]        # 使用的技能序列
    
    def __lt__(self, other):
        """用于优先队列排序"""
        return self.rounds_used < other.rounds_used

class BossBattleOptimizer:
    """BOSS战策略优化器"""
    
    def __init__(self, initial_boss_hp: int, initial_player_resources: int, 
                 max_rounds: int = 20):
        self.initial_boss_hp = initial_boss_hp
        self.initial_player_resources = initial_player_resources
        self.max_rounds = max_rounds
        
        # 定义技能库
        self.skills = {
            "普通攻击": Skill("普通攻击", damage=5, cost=0, cooldown=0, 
                           description="基础攻击，无消耗无冷却"),
            "大招": Skill("大招", damage=10, cost=3, cooldown=2, 
                        description="高伤害技能，消耗3资源，冷却2回合"),
            "连击": Skill("连击", damage=7, cost=2, cooldown=1,
                        description="中等伤害技能，消耗2资源，冷却1回合"),
            "爆发": Skill("爆发", damage=15, cost=5, cooldown=4,
                        description="超高伤害技能，消耗5资源，冷却4回合")
        }
        
        self.best_solution = None
        self.best_rounds = float('inf')
        
    def calculate_heuristic(self, state: GameState) -> float:
        """
        启发式函数：估算从当前状态到胜利需要的最少回合数
        f(n) = 已用回合数 + 预估剩余回合数
        """
        if state.boss_hp <= 0:
            return state.rounds_used
        
        # 计算平均每回合伤害（考虑技能可用性和资源限制）
        available_damages = []
        
        # 普通攻击总是可用
        available_damages.append(self.skills["普通攻击"].damage)
        
        # 检查其他技能是否可用
        for skill_name, skill in self.skills.items():
            if (skill_name not in state.skill_cooldowns or 
                state.skill_cooldowns[skill_name] <= 0):
                if state.player_resources >= skill.cost:
                    available_damages.append(skill.damage)
        
        # 计算平均伤害（加权平均，高伤害技能权重更大）
        if available_damages:
            # 使用最大伤害作为乐观估计
            max_damage = max(available_damages)
            estimated_rounds = state.boss_hp / max_damage
        else:
            # 只能使用普通攻击
            estimated_rounds = state.boss_hp / self.skills["普通攻击"].damage
        
        return state.rounds_used + estimated_rounds
    
    def get_available_skills(self, state: GameState) -> List[str]:
        """获取当前状态下可用的技能"""
        available = []
        
        for skill_name, skill in self.skills.items():
            # 检查冷却时间
            if (skill_name in state.skill_cooldowns and 
                state.skill_cooldowns[skill_name] > 0):
                continue
                
            # 检查资源消耗
            if state.player_resources < skill.cost:
                continue
                
            available.append(skill_name)
        
        return available
    
    def apply_skill(self, state: GameState, skill_name: str) -> GameState:
        """应用技能，返回新状态"""
        skill = self.skills[skill_name]
        new_state = GameState(
            boss_hp=state.boss_hp - skill.damage,
            player_resources=state.player_resources - skill.cost,
            rounds_used=state.rounds_used + 1,
            skill_cooldowns=deepcopy(state.skill_cooldowns),
            skill_sequence=state.skill_sequence + [skill_name]
        )
        

        
        # 设置技能冷却
        if skill.cooldown > 0:
            new_state.skill_cooldowns[skill_name] = skill.cooldown
        
        # 减少所有技能的冷却时间
        for skill_name_cd in new_state.skill_cooldowns:
            if new_state.skill_cooldowns[skill_name_cd] > 0:
                new_state.skill_cooldowns[skill_name_cd] -= 1
        
        return new_state
    
    def branch_and_bound(self) -> Optional[Tuple[List[str], int]]:
        """
        分支限界算法主函数
        返回：(最优技能序列, 最少回合数) 或 None
        """
        print(f"🎯 开始BOSS战策略优化")
        print(f"初始条件：BOSS血量={self.initial_boss_hp}, 玩家资源={self.initial_player_resources}")
        print(f"最大回合限制：{self.max_rounds}")
        print()
        
        # 初始状态
        initial_state = GameState(
            boss_hp=self.initial_boss_hp,
            player_resources=self.initial_player_resources,
            rounds_used=0,
            skill_cooldowns={},
            skill_sequence=[]
        )
        
        # 优先队列：(代价函数值, 状态)
        priority_queue = [(self.calculate_heuristic(initial_state), initial_state)]
        
        explored_count = 0
        pruned_count = 0
        
        while priority_queue:
            current_cost, current_state = heapq.heappop(priority_queue)
            explored_count += 1
            
            # 剪枝：如果当前代价已经超过最优解，跳过
            if current_cost >= self.best_rounds:
                pruned_count += 1
                continue
            
            # 剪枝：超过最大回合限制
            if current_state.rounds_used >= self.max_rounds:
                pruned_count += 1
                continue
            
            # 检查是否达到胜利条件
            if current_state.boss_hp <= 0:
                if current_state.rounds_used < self.best_rounds:
                    self.best_rounds = current_state.rounds_used
                    self.best_solution = current_state.skill_sequence
                    print(f"✨ 找到更优解：{current_state.rounds_used}回合")
                continue
            
            # 获取可用技能并扩展分支
            available_skills = self.get_available_skills(current_state)
            
            for skill_name in available_skills:
                # 生成新状态
                new_state = self.apply_skill(current_state, skill_name)
                
                # 计算新状态的代价函数
                new_cost = self.calculate_heuristic(new_state)
                
                # 剪枝：如果预估代价超过最优解，不加入队列
                if new_cost < self.best_rounds:
                    heapq.heappush(priority_queue, (new_cost, new_state))
                else:
                    pruned_count += 1
        
        print(f"\n📊 搜索统计：")
        print(f"探索节点数：{explored_count}")
        print(f"剪枝节点数：{pruned_count}")
        
        if self.best_solution:
            return self.best_solution, int(self.best_rounds)
        else:
            return None
    
    def analyze_solution(self, skill_sequence: List[str]) -> List[Dict]:
        """分析解决方案的详细过程"""
        print(f"\n🔍 解决方案分析：")
        
        state = GameState(
            boss_hp=self.initial_boss_hp,
            player_resources=self.initial_player_resources,
            rounds_used=0,
            skill_cooldowns={},
            skill_sequence=[]
        )
        
        analysis = []
        
        for round_num, skill_name in enumerate(skill_sequence, 1):
            skill = self.skills[skill_name]
            
            # 记录回合开始状态
            round_info = {
                "回合": round_num,
                "技能": skill_name,
                "伤害": skill.damage,
                "消耗": skill.cost,
                "BOSS血量前": state.boss_hp,
                "玩家资源前": state.player_resources
            }
            
            # 应用技能
            state = self.apply_skill(state, skill_name)
            
            # 记录回合结束状态
            round_info.update({
                "BOSS血量后": state.boss_hp,
                "玩家资源后": state.player_resources,
                "技能冷却": dict(state.skill_cooldowns)
            })
            
            analysis.append(round_info)
            
            print(f"回合{round_num}: 使用{skill_name} -> "
                  f"BOSS血量{round_info['BOSS血量前']}→{round_info['BOSS血量后']}, "
                  f"玩家资源{round_info['玩家资源前']}→{round_info['玩家资源后']}")
        
        return analysis
    
    def save_result(self, filename: str):
        """保存优化结果到JSON文件"""
        if not self.best_solution:
            print("❌ 没有找到解决方案")
            return
        
        result = {
            "初始条件": {
                "BOSS血量": self.initial_boss_hp,
                "玩家资源": self.initial_player_resources,
                "最大回合": self.max_rounds
            },
            "最优解": {
                "技能序列": self.best_solution,
                "总回合数": self.best_rounds,
                "平均每回合伤害": self.initial_boss_hp / self.best_rounds
            },
            "技能库": {name: {
                "伤害": skill.damage,
                "消耗": skill.cost,
                "冷却": skill.cooldown,
                "描述": skill.description
            } for name, skill in self.skills.items()},
            "详细分析": self.analyze_solution(self.best_solution)
        }
        
        with open(filename, 'w', encoding='utf-8') as f:
            json.dump(result, f, ensure_ascii=False, indent=2)
        
        print(f"\n💾 结果已保存到 {filename}")


def optimize_boss_battle(boss_hp: int, player_resources: int, max_rounds: int = 20):
    """BOSS战优化主函数"""
    optimizer = BossBattleOptimizer(boss_hp, player_resources, max_rounds)
    
    result = optimizer.branch_and_bound()
    
    if result:
        skill_sequence, rounds = result
        print(f"\n🎉 找到最优策略！")
        print(f"最少回合数：{rounds}")
        print(f"技能序列：{' -> '.join(skill_sequence)}")
        
        # 分析解决方案
        optimizer.analyze_solution(skill_sequence)
        
        # 保存结果
        optimizer.save_result("boss_battle_strategy.json")
        
        return skill_sequence, rounds
    else:
        print(f"\n❌ 在{max_rounds}回合内无法击败BOSS")
        print("建议：增加初始资源或提高回合限制")
        return None


if __name__ == "__main__":
    print("=== BOSS战策略优化器 - 分支限界算法 ===")
    print("🎯 目标：寻找最小回合数的技能序列击败BOSS")
    print()
    
    # 测试案例1：中等难度
    print("📋 测试案例1：中等难度BOSS")
    optimize_boss_battle(boss_hp=50, player_resources=15, max_rounds=15)
    
    print("\n" + "="*60)
    
    # 测试案例2：高难度
    print("📋 测试案例2：高难度BOSS") 
    optimize_boss_battle(boss_hp=80, player_resources=20, max_rounds=20)
    
    print("\n" + "="*60)
    
    # 测试案例3：资源紧张
    print("📋 测试案例3：资源紧张")
    optimize_boss_battle(boss_hp=40, player_resources=8, max_rounds=12) 